/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
 * @author zhong
 *
 */
public class GuesstheWord {
	public void findSecretWord(String[] wordlist, Master master) {
		Set<String> words = new HashSet<>();
		for (String word : wordlist)
			words.add(word);
		int cnt = 0;
		while (true) {
			System.out.println("剩余满足条件的 " + words);
			String cur = words.iterator().next();
			int match = master.guess(cur);
			if (match == 6) {
				System.out.println("找到" + cur);
				break;
			}
			List<String> exclude = new ArrayList<>();
			for (String word : words) {
				if (getDiff(word, cur) != match)
					exclude.add(word);
			}
			words.removeAll(exclude);
			cnt++;
			if (cnt > 10)
				break;
		}
	}

	public void findSecretWordM(String[] wordlist, Master master) {
		int n = wordlist.length;
		int[][] sim = new int[n][n];
		for (int i = 0; i < wordlist.length; i++) {
			for (int j = i + 1; j < wordlist.length; j++) {
				int c = getDiff(wordlist[i], wordlist[j]);
				sim[i][j] = sim[j][i] = c;
			}
		}
		boolean[] visited = new boolean[n];
		ArrayList<Integer> index = new ArrayList<>();
		ArrayList<Integer> simCondition = new ArrayList<>();
		int guessTimes = 0;
		Random random = new Random();
		while (true) {
			// 找和c有指定相似度的
			int i = random.nextInt(n);
			if (!visited[i]) {
				if (satisfyCondition(index, simCondition, sim, i, visited)) {// 满足之前所有的条件
					int c = master.guess(wordlist[i]);
					guessTimes++;
					System.out.println("guess " + guessTimes + " : " + i + "  " + wordlist[i] + " re " + c);
					visited[i] = true;
					index.add(i);
					simCondition.add(c);
					if (c == 6) {
						System.out.println("找到" + wordlist[i]);
						return;
					}
					if (guessTimes == 10) {
						System.out.println("没找到");
						return;
					}
				}

			}
		}

	}

	/**
	 * 满足目标条件，所有相似度满足
	 * 
	 * @param index
	 * @param simCondition
	 * @param sim
	 * @param i
	 * @return
	 */
	private boolean satisfyCondition(ArrayList<Integer> index, ArrayList<Integer> simCondition, int[][] sim, int i,
			boolean[] visited) {
		for (int j = 0; j < index.size(); j++) {
			int id = index.get(j);
			int simC = simCondition.get(j);
			if (sim[i][id] != simC) {
				visited[i] = true;// 不可能
				return false;
			}
		}
		return true;
	}

	private int getDiff(String string, String string2) {
		int cnt = 0;
		for (int i = 0; i < 6; i++) {
			if (string.charAt(i) == string2.charAt(i)) {
				cnt++;
			}
		}
		return cnt;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String secret = "ccoyyo";
		String[] wordList = { "wichbx", "oahwep", "tpulot", "eqznzs", "vvmplb", "eywinm", "dqefpt", "kmjmxr", "ihkovg",
				"trbzyb", "xqulhc", "bcsbfw", "rwzslk", "abpjhw", "mpubps", "viyzbc", "kodlta", "ckfzjh", "phuepp",
				"rokoro", "nxcwmo", "awvqlr", "uooeon", "hhfuzz", "sajxgr", "oxgaix", "fnugyu", "lkxwru", "mhtrvb",
				"xxonmg", "tqxlbr", "euxtzg", "tjwvad", "uslult", "rtjosi", "hsygda", "vyuica", "mbnagm", "uinqur",
				"pikenp", "szgupv", "qpxmsw", "vunxdn", "jahhfn", "kmbeok", "biywow", "yvgwho", "hwzodo", "loffxk",
				"xavzqd", "vwzpfe", "uairjw", "itufkt", "kaklud", "jjinfa", "kqbttl", "zocgux", "ucwjig", "meesxb",
				"uysfyc", "kdfvtw", "vizxrv", "rpbdjh", "wynohw", "lhqxvx", "kaadty", "dxxwut", "vjtskm", "yrdswc",
				"byzjxm", "jeomdc", "saevda", "himevi", "ydltnu", "wrrpoc", "khuopg", "ooxarg", "vcvfry", "thaawc",
				"bssybb", "ccoyyo", "ajcwbj", "arwfnl", "nafmtm", "xoaumd", "vbejda", "kaefne", "swcrkh", "reeyhj",
				"vmcwaf", "chxitv", "qkwjna", "vklpkp", "xfnayl", "ktgmfn", "xrmzzm", "fgtuki", "zcffuv", "srxuus",
				"pydgmq" };
		Master master = new Master();
		master.wordlist = wordList;
		master.secret = secret;
		new GuesstheWord().findSecretWord(wordList, master);
		new GuesstheWord().findSecretWordM(wordList, master);

	}

}
